package 图.无向图;

import 抽象数据类型.Graph;

/**
 * @description:
 * @author: ywk
 * @date: 2021-07-27
 */
public class 判断图是二分图 {
    public static void main(String[] args) {
        int[] arr1 = {0, 1,2 };
        int[] arr2 = {1, 2,0};
        Graph G = new Graph(arr1.length);
        G.addGraph(arr1, arr2);
        TwoColor cc = new TwoColor(G);
        System.out.println(cc.isTwoColorable);
    }
    public static class TwoColor {
        private boolean[] marked;
        private boolean[] color;
        private boolean isTwoColorable = true;

        public TwoColor(Graph graph) {
            marked = new boolean[graph.V()];
            color = new boolean[graph.V()];
            for (int s = 0; s < graph.V(); s++) {
                if (!marked[s]) {
                    dfs(graph, s);
                }
            }
        }

        private void dfs(Graph graph, int v) {
            marked[v] = true;
            for (Integer w : graph.adj(v)) {
                if (!marked[w]) {
                    color[w] = !color[v];
                    dfs(graph, w);
                } else if (color[w] == color[v]) {
                    isTwoColorable = false;
                }
            }
        }

        public Boolean isBipartite() {
            return isTwoColorable;
        }
    }
}